Mix-net is an operation of substituting and decrypting the elements of an input ciphertext sequence such that the correspondence between the elements of an output decrypted text sequence and those of the input ciphertext sequence becomes unnoticeable.
[Prior Art (1)]
In a conventional mix-net, a method using a proof apparatus and a verification apparatus is used to make it possible to specify an organization which has not executed the correct operation and specify the fact (e.g., Japanese Patent Laid-Open No. 2002-344445 (reference 1)). This method will be described with reference to FIG. 8.
The proof apparatus of reference 1 proves that substitution and decryption are correctly done. The verification apparatus of reference 1 verifies that the proof executed by the proof apparatus is correct. With the functions of the two apparatuses, if the proof apparatus does not execute the correct operation (substitution and decryption), proof fails, and the verification apparatus can determine that the proof apparatus has not correctly operated.
The proof apparatus and verification apparatus of reference 1 are used in the following way and operated as a mix-net as a whole. First, a private key 906 is determined in correspondence with each substitution/decryption apparatus 912. A public key 901 is generated from the private key 906 and distributed to all participant apparatuses 903. Each participant apparatus 903 encrypts a short plaintext 902 having a predetermined length by using the public key 901.
Each substitution/decryption apparatus 912 substitutes and decrypts an input ciphertext sequence 913 and transfers it to the next substitution/decryption apparatus 912 (processing 907). This operation is repeated to finally obtain a plaintext sequence 911. The substitution/decryption apparatus 912 proves by using the proof apparatus of reference 1 that the substitution and decryption operations executed by itself are correct (processing 908). A verification apparatus 909 verifies, by using the verification apparatus of reference 1, the proof executed by the substitution/decryption apparatus. Even a third party can execute this verification when it can prepare the verification apparatus.
In the above method, the length of the plaintext 902 that the participant apparatus 903 can encrypt is limited to almost the same as the length of the public key. Hence, a longer plaintext cannot be processed.
[Prior Art (2)]
In another conventional mix-net, a method by Juels and Jakobsson is used to make it possible to process a ciphertext having an arbitrary length (e.g., “An Optimally Robust Hybrid Mix Network, Proc. of the 20th annual ACM Symposium on Principles of Distributed Computation, 2001” (reference 2)). In this method, a ciphertext to be input is created by encrypting a plaintext by arbitrary secret key cryptography. Hence, the length of the plaintext is not particularly limited. Additionally, in this method, if one of a plurality of organizations to decrypt and shuffle ciphertexts has not correctly executed these operations, it can be specified by the organizations which execute encryption and shuffle in cooperation. However, a third party not in cooperation with the plurality of organizations cannot specify the organization which has not correctly execute the ciphertext operation.
The above relationship will be described with reference to FIG. 9. The mix-net of reference 2 operates in almost the same way as the mix-net of the prior art (1) except that a long plaintext 1002 may be input. In addition, the substitution/decryption apparatuses can verify each other whether substitution and decryption have been done correctly (processing 1014). However, any third party cannot verify it, unlike the prior art (1).